template<class K>
struct HashFun
{
	size_t operator()(const K& k)
	{
		return (size_t)k;
	}
};
template<>
struct HashFun<string>
{
	size_t operator()(const string& s)
	{
		size_t num = 0;
		for (size_t i = 0; i < s.size(); i++)
			num += s[i];
		return num;
	}
};

namespace HashBucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	template<class K, class T, class Hash, class KeyOfT>
	class _HashTable;

	template<class K, class T, class Hash, class KeyOfT>
	struct __HashTable_Iterator
	{
		typedef HashNode<T> Node;
		typedef __HashTable_Iterator<K, T, Hash, KeyOfT> Self;
		typedef _HashTable<K, T, Hash, KeyOfT> HT;
		typedef T& reference;
		typedef T* pointer;

		Node* _cur;
		HT* _ht;

		__HashTable_Iterator(Node* node, HT* ht) :_cur(node), _ht(ht) {}

		bool operator==(const Self& s) { return _cur == s._cur; }
		bool operator!=(const Self& s) { return _cur != s._cur; }

		reference operator*() { return _cur->_data; }
		pointer operator->() { return &_cur->_data; }

		Self& operator++()
		{
			if (_cur->_next)
				_cur = _cur->_next;
			else
			{
				Hash hash;
				KeyOfT kft;

				size_t hashi = hash(kft(_cur->_data)) % _ht->TablesSize();
				size_t i = hashi + 1;
				for (; i < _ht->TablesSize(); i++)
				{
					if (_ht->_tables[i])
					{
						_cur = _ht->_tables[i];
						break;
					}
				}

				if (i == _ht->TablesSize())
					_cur = nullptr;
			}

			return *this;
		}
		Self operator++(int)
		{
			Self tmp(_cur, _ht);
			++*this;
			return tmp;
		}

		Self operator+(size_t k)
		{
			Self tmp(_cur, _ht);
			while (k--)
			{
				++tmp;
			}
			return tmp;
		}
	};

	template<class K, class T, class Hash, class KeyOfT>
	class _HashTable
	{
		typedef HashNode<T> Node;

	    template<class K, class T, class Hash, class KeyOfT>
		friend struct __HashTable_Iterator;
	public:
		typedef __HashTable_Iterator<K, T, Hash, KeyOfT> iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
				if (_tables[i])
					return iterator(_tables[i], this);
			return iterator(nullptr, this);
		}
		iterator end() { return iterator(nullptr, this); }

		pair<iterator, bool> insert(const T& data)
		{
			Hash hash;
			KeyOfT kft;

			iterator tmp = find(kft(data));
			if (tmp != end())
				return make_pair(tmp, false);

			if (_tables.size() == _size)
			{
				vector<Node*> newTables;
				newTables.resize(__stl_next_prime(_tables.size()), nullptr);

				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];

					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hash(kft(cur->_data)) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			size_t hashi = hash(kft(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_size;

			return make_pair(iterator(newnode, this), true);
		}

		iterator find(const K& key)
		{
			if (empty())
				return iterator(nullptr, this);

			KeyOfT kft;
			Hash hash;

			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kft(cur->_data) == key)
					return iterator(cur, this);
				cur = cur->_next;
			}
			return iterator(nullptr, this);
		}

		bool erase(const K& key)
		{
			assert(!empty());
			if (find(key) == end())
				return false;

			Hash hash;
			KeyOfT kft;

			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (kft(cur->_data) == key)
				{
					if (cur == _tables[hashi])
					{
						Node* next = cur->_next;
						delete cur;
						_tables[hashi] = next;
					}
					else
					{
						prev->_next = cur->_next;
						delete cur;
					}
					break;
				}
				else
				{
					prev = cur;
				}
				cur = cur->_next;
			}
			--_size;

			return true;
		}

		bool empty() const { return _tables.size() == 0; }

		~_HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						delete cur;
						cur = next;
					}
				}
			}
		}

		inline size_t __stl_next_prime(size_t n)
		{
			static const size_t __stl_num_primes = 28;
			static const size_t __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < __stl_num_primes; ++i)
				if (__stl_prime_list[i] > n)
					return __stl_prime_list[i];

			return -1;
		}

		size_t size() const { return _size; }
		size_t TablesSize() const { return _tables.size(); }
		size_t BucketNum() const 
		{
			size_t num = 0;
			for (size_t i = 0; i < _tables.size(); i++)
				if (_tables[i])
					num++;
			return num;
		}
		size_t MaxBucketLenth() const
		{
			size_t maxlen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					size_t tmplen = 0;
					Node* cur = _tables[i];
					while (cur)
					{
						cur = cur->_next;
						tmplen++;
					}
					maxlen = max(maxlen, tmplen);
				}
			}
			return maxlen;
		}

	private:
		vector<Node*> _tables;
		size_t _size = 0;
	};

	//void TestHT3()
	//{

	//	int n = 19000000;
	//	vector<int> v;
	//	v.reserve(n);
	//	srand(time(0));
	//	for (int i = 0; i < n; ++i)
	//	{
	//		v.push_back(i);
	//		v.push_back(rand() + i);  // 重复少
	//		v.push_back(rand());  // 重复多
	//	}

	//	size_t begin1 = clock();
	//	_HashTable<int, int> ht;
	//	for (auto e : v)
	//	{
	//		ht.insert(make_pair(e, e));
	//	}
	//	size_t end1 = clock();

	//	cout << "数据个数:" << ht.size() << endl;
	//	cout << "表的长度:" << ht.TablesSize() << endl;
	//	cout << "桶的个数:" << ht.BucketNum() << endl;
	//	cout << "平均每个桶的长度:" << (double)ht.size() / (double)ht.BucketNum() << endl;
	//	cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl;
	//	cout << "负载因子:" << (double)ht.size() / (double)ht.TablesSize() << endl;
	//}
}
